package com.nccs.arithmetic;

import java.util.Arrays;

/**
 * @author xuzengsheng
 * @program nssc-parent
 * @createTime 2021-09-14- 17:41:00
 * @description 计数排序
 */

public class CountSort extends AbstractSortHandler {


    public CountSort(String arithmeticName) {
        super(arithmeticName);
    }

    public static void main(String[] args) {
        new CountSort("计数排序").execute();
    }

    @Override
    public void sort(int[] arry) {
        countSort(arry);
    }

    public static void countSort(int[] arr) {
        if (arr == null || arr.length == 0)
            return;

        int max = max(arr);

        int[] count = new int[max + 1];

        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }

        int k = 0;
        for (int i = 0; i <= max; i++) {
            for (int j = 0; j < count[i]; j++) {
                arr[k++] = i;
            }
        }

    }

    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int ele : arr) {
            if (ele > max)
                max = ele;
        }

        return max;
    }

}
